#define _CRT_SECURE_NO_WARNINGS 1



class Solution
{
    vector<vector<string>> ret;
    vector<string> v;
    bool vcol[9];
    bool forwarddiagonal[18];
    bool backdiagonal[18];
    int num;

    void dfs(int level)
    {
        if (level == num)
        {
            ret.push_back(v);
            return;
        }
        for (int i = 0; i < num; i++)
        {
            if (!vcol[i] && !forwarddiagonal[level + i] && !backdiagonal[i - level + num])
            {
                vcol[i] = true;
                forwarddiagonal[level + i] = true;
                backdiagonal[num + i - level] = true;
                v[level][i] = 'Q';
                dfs(level + 1);
                vcol[i] = false;
                forwarddiagonal[level + i] = false;
                backdiagonal[num + i - level] = false;
                v[level][i] = '.';
            }
        }

    }

public:
    vector<vector<string>> solveNQueens(int n)
    {
        num = n;
        v.resize(n, string(n, '.'));
        dfs(0);
        return ret;
    }
};

class Solution
{
    vector<vector<string>> ret;
    vector<string> v;
    int n;
public:

    bool check(string& s)
    {
        int l = 0, r = s.size() - 1;
        while (l < r)
        {
            if (s[l] != s[r]) return false;
            l++, r--;
        }

        return true;
    }

    void dfs(int pos, const string& s)
    {
        if (pos >= n)
        {
            ret.push_back(v);
            return;
        }

        for (int i = pos; i < n; i++)
        {
            string tmp = s.substr(pos, i - pos + 1);
            if (check(tmp))
            {
                v.push_back(tmp);
                dfs(i + 1, s);
                v.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s)
    {
        n = s.size();
        dfs(0, s);
        return ret;
    }
};

class Solution {
public:
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int row, col, n;
    bool vis[6][6];

    bool dfs(int i, int j, int pos, vector<vector<char>>& board, string word)
    {
        if (pos == n) return true;

        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && !vis[x][y] && board[x][y] == word[pos])
            {
                vis[x][y] = true;
                if (dfs(x, y, pos + 1, board, word)) return true;
                vis[x][y] = false;
            }
        }

        return false;
    }

    bool exist(vector<vector<char>>& board, string word)
    {
        row = board.size(), col = board[0].size(), n = word.size();
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if (dfs(i, j, 1, board, word)) return true;
                    vis[i][j] = false;
                }

            }

        return false;
    }
};

class Solution
{
    vector<string> ret;
    string s;
    int c[2];

public:
    vector<string> generateParenthesis(int n)
    {
        dfs(n);
        return ret;
    }
    void dfs(int n)
    {
        if (s.size() == n * 2)
        {
            ret.push_back(s);
        }

        if (c[0] < n)
        {
            s += '(';
            c[0]++;
            dfs(n);
            s.pop_back();
            c[0]--;
        }

        if (c[1] < c[0])
        {
            s += ')';
            c[1]++;
            dfs(n);
            s.pop_back();
            c[1]--;
        }
    }
};


class Solution
{
    vector<vector<int>> ret;
    vector<int> tmp;
    int n;
    int aim;
public:

    void dfs(int sum, int pos, vector<int>& candidates)
    {
        if (sum >= aim)
        {
            if (sum == aim)ret.push_back(tmp);
            return;
        }
        for (int i = pos; i < n; i++)
        {
            tmp.push_back(candidates[i]);
            dfs(sum + candidates[i], i, candidates);
            tmp.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        aim = target;
        n = candidates.size();
        dfs(0, 0, candidates);
        return ret;
    }
};


string chars[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
class Solution
{
    string s;
    int n;
    vector<string> ret;
public:
    void dfs(int level, const string& digits)
    {
        if (level == n)
        {
            ret.push_back(s);
            return;
        }

        int index = digits[level] - '0';
        for (int i = 0; i < chars[index].size(); i++)
        {
            s += chars[index][i];
            dfs(level + 1, digits);
            s.pop_back();
        }
    }

    vector<string> letterCombinations(string digits)
    {
        n = digits.size();
        if (n > 0) dfs(0, digits);
        return ret;
    }
};


class Solution
{
    vector<vector<int>> ret;
    vector<int> v;
    int n;
public:
    void dfs(int level, vector<int>& nums)
    {
        ret.push_back(v);
        if (level == n)
        {
            return;
        }
        for (int i = level; i < n; i++)
        {
            v.push_back(nums[i]);
            dfs(i + 1, nums);
            v.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums)
    {
        n = nums.size();
        dfs(0, nums);
        return ret;
    }
};



class Solution
{
    vector<vector<int>> ret;
    bool vis[6];
    vector<int> v;
    int n;
public:
    void dfs(vector<int>& nums, int level)
    {
        if (level == n)
        {
            ret.push_back(v);
        }

        for (int i = 0; i < n; i++)
        {
            if (vis[i]) continue;

            vis[i] = true;
            v.push_back(nums[i]);
            dfs(nums, level + 1);
            v.pop_back();
            vis[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums)
    {
        n = nums.size();
        dfs(nums, 0);
        return ret;
    }
};



class Trie
{
    vector<Trie*> children;
    bool end;
public:
    Trie() :children(26), end(false)
    {}

    void insert(string word)
    {
        Trie* pnode = this;
        for (auto c : word)
        {
            int index = c - 'a';
            if (pnode->children[index])
            {
                pnode = pnode->children[index];
            }
            else
            {
                Trie* newnode = new Trie();
                pnode->children[index] = newnode;
                pnode = newnode;
            }
        }
        pnode->end = true;
    }

    bool search(string word)
    {
        Trie* pnode = SearchPrefixNode(word);
        return pnode != nullptr && pnode->end;
    }

    bool startsWith(string prefix)
    {
        Trie* pnode = SearchPrefixNode(prefix);
        return pnode != nullptr;
    }

    Trie* SearchPrefixNode(const string& prefix)
    {
        Trie* pnode = this;
        for (auto c : prefix)
        {
            int index = c - 'a';
            if (pnode->children[index] == nullptr)
            {
                return nullptr;
            }
            else pnode = pnode->children[index];
        }

        return pnode;
    }

};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> e[2000];
        queue<int> q;
        int indegree[2000] = { 0 };


        for (auto& v : prerequisites)
        {
            e[v[1]].push_back(v[0]);
            indegree[v[0]]++;
        }

        for (int i = 0; i < numCourses; i++)
        {
            if (indegree[i] == 0)
                q.push(i);
        }

        int total = 0;
        while (!q.empty())
        {
            int front = q.front();
            q.pop();
            total++;
            for (auto e : e[front])
            {
                indegree[e]--;
                if (indegree[e] == 0)
                    q.push(e);
            }
        }


        return total == numCourses;
    }
};


class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid)
    {
        int sum = 0;
        queue<pair<int, int>> q;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 2)
                {
                    q.push({ i,j });
                }
                else if (grid[i][j] == 1) sum++;
            }

        int ret = 0;
        int dx[4] = { 0,0,-1,1 };
        int dy[4] = { 1,-1,0,0 };
        while (!q.empty())
        {
            if (sum == 0) break;
            int sz = q.size();
            while (sz--)
            {
                auto p = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = p.first + dx[k], y = p.second + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
                    {
                        grid[x][y] = 2;
                        q.push({ x,y });
                        sum--;
                    }
                }
            }
            ret++;
        }

        return sum == 0 ? ret : -1;
    }
};


class Solution
{
    int m, n;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    bool check[300][300];
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == '1')
            {
                check[x][y] = true;
                dfs(grid, x, y);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid)
    {
        m = grid.size();
        n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!check[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    check[i][j] = true;
                    dfs(grid, i, j);
                }
            }
        }

        return ret;
    }
};
